// https://www.lintcode.com/problem/paint-house-ii/description

class Solution {
public:
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
    int minCostII(vector<vector<int>> &costs) {
        if (costs.empty()) return 0;
        int n = costs.size();
        int types = costs[0].size();
        int res = INT_MAX;
        vector<vector<int>> rec(n, vector<int>(types, INT_MAX));
        for (int i = 0; i < types; ++i) {
            rec[0][i] = costs[0][i];
        }
        for (int i = 1; i < n; ++i) {
            int min_idx1 = -1;
            int min_idx2 = -1;
            for (int j = 0; j < types; ++j) {
                if (min_idx1 == -1 || rec[i - 1][j] < rec[i - 1][min_idx1]) {
                    min_idx2 = min_idx1;
                    min_idx1 = j;
                }
                else if (min_idx2 == -1 || rec[i - 1][j] < rec[i - 1][min_idx2]) min_idx2 = j;
            }
            for (int j = 0; j < types; ++j) {
                if (min_idx1 != j) rec[i][j] = rec[i - 1][min_idx1];
                else rec[i][j] = rec[i - 1][min_idx2];
                rec[i][j] += costs[i][j];
            }
        }
        for (int i = 0; i < types; ++i) {
            res = min(res, rec[n - 1][i]);
        }
        return res;
    }
};


class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;
        int n = costs.size();
        int types = costs[0].size();
        int res = INT_MAX;
        vector<vector<int>> rec(n, vector<int>(types, INT_MAX));
        for (int i = 0; i < types; ++i) {
            rec[0][i] = costs[0][i];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < types; ++j) {
                for (int t = 1; t < types; ++t)
                    rec[i][j] = min(rec[i - 1][(j + t) % types], rec[i][j]);
                rec[i][j] += costs[i][j];
            }
        }
        for (int i = 0; i < types; ++i) {
            res = min(rec[n - 1][i], res);
        }
        return res;
    }
};